﻿using System.Collections.Generic;
using System.Runtime.CompilerServices;

namespace KewlStuff.DataStructures
{
    /// <summary>
    /// An LRU Cache based on http://stackoverflow.com/a/3719378/175308
    /// </summary>
    /// <typeparam name="TK"></typeparam>
    /// <typeparam name="TV"></typeparam>
    public class LruCache<TK, TV>
    {
        readonly int capacity;
        readonly Dictionary<TK, LinkedListNode<LruCacheItem<TK, TV>>> cacheMap = new Dictionary<TK, LinkedListNode<LruCacheItem<TK, TV>>>();
        readonly LinkedList<LruCacheItem<TK, TV>> lruList = new LinkedList<LruCacheItem<TK, TV>>();

        public LruCache(int capacity)
        {
            this.capacity = capacity;
        }

        [MethodImpl(MethodImplOptions.Synchronized)]
        public TV Get(TK key)
        {
            LinkedListNode<LruCacheItem<TK, TV>> node;
            if (cacheMap.TryGetValue(key, out node))
            {
                TV value = node.Value.Value;

                lruList.Remove(node);
                lruList.AddLast(node);
                return value;
            }
            return default(TV);
        }

        [MethodImpl(MethodImplOptions.Synchronized)]
        public void Add(TK key, TV val)
        {
            // if it's already in the cache, update the value and move in the list
            LinkedListNode<LruCacheItem<TK, TV>> node;
            if (cacheMap.TryGetValue(key, out node))
            {
                node.Value.Value = val;
                lruList.Remove(node);
                lruList.AddLast(node);
                return;
            }


            if (cacheMap.Count >= capacity)
            {
                RemoveFirst();
            }
            var cacheItem = new LruCacheItem<TK, TV>(key, val);
            node = new LinkedListNode<LruCacheItem<TK, TV>>(cacheItem);
            cacheMap.Add(key, node);
            lruList.AddLast(node);
        }


        protected void RemoveFirst()
        {
            var node = lruList.First;
            lruList.RemoveFirst();
            cacheMap.Remove(node.Value.Key);
        }

        public TV this[TK key]
        {
            get { return Get(key); }
            set { Add(key, value); }
        }
    }


    internal class LruCacheItem<TK, TV>
    {
        public LruCacheItem(TK k, TV v)
        {
            Key = k;
            Value = v;
        }
        public TK Key;
        public TV Value;
    }
}
